[Chapter Nine][Previous] [Next]
[Art of Assembly][Randall
Hyde]
Art of Assembly: Chapter Nine
- 9.2 - Logical (Boolean) Expressions
9.2 Logical (Boolean) Expressions
Consider the following expression from a Pascal program:
B := ((X=Y) and (A <= C)) or ((Z-A) <> 5);
B is a boolean variable and the remaining variables are all
integers.
How do we represent boolean variables in assembly language? Although it
takes only a single bit to represent a boolean value, most assembly language
programmers allocate a whole byte or word for this purpose. With a byte,
there are 256 possible values we can use to represent the two values true
and false. So which two values (or which two sets of values) do we use to
represent these boolean values? Because of the machine's architecture, it's
much easier to test for conditions like zero or not zero and positive or
negative rather than to test for one of two particular boolean values. Most
programmers (and, indeed, some programming languages like "C")
choose zero to represent false and anything else to represent true. Some
people prefer to represent true and false with one and zero (respectively)
and not allow any other values. Others select 0FFFFh for true and 0 for
false. You could also use a positive value for true and a negative value
for false. All these mechanisms have their own advantages and drawbacks.
Using only zero and one to represent false and true offers one very big
advantage: the 80x86 logical instructions (and, or, xor and,
to a lesser extent, not) operate on these values exactly as
you would expect. That is, if you have two boolean variables A
and B, then the following instructions perform the basic logical
operations on these two variables:
mov ax, A
and ax, B
mov C, ax ;C := A and B;
mov ax, A
or ax, B
mov C, ax ;C := A or B;
mov ax, A
xor ax, B
mov C, ax ;C := A xor B;
mov ax, A ;Note that the NOT instruction does not
not ax ; properly compute B := not A by itself.
and ax, 1 ; I.e., (NOT 0)does not equal one.
mov B, ax ;B := not A;
mov ax, A ;Another way to do B := NOT A;
xor ax, 1
mov B, ax ;B := not A;
Note, as pointed out above, that the not instruction will not
properly compute logical negation. The bitwise not of zero is 0FFh and the
bitwise not of one is 0FEh. Neither result is zero or one. However, by anding
the result with one you get the proper result. Note that you can implement
the not operation more efficiently using the xor ax,
1 instruction since it only affects the L.O. bit.
As it turns out, using zero for false and anything else for true has a lot
of subtle advantages. Specifically, the test for true or false is often
implicit in the execution of any logical instruction. However, this mechanism
suffers from a very big disadvantage: you cannot use the 80x86 and,
or, xor, and not instructions to implement the boolean
operations of the same name. Consider the two values 55h and 0AAh. They're
both non-zero so they both represent the value true. However, if you logically
and 55h and 0AAh together using the 80x86 and instruction,
the result is zero. (True and true) should produce true, not false. A system
that uses non-zero values to represent true and zero to represent false
is an arithmetic logical system. A system that uses the two distinct values
like zero and one to represent false and true is called a boolean logical
system, or simply a boolean system. You can use either system, as convenient.
Consider again the boolean expression:
B := ((X=Y) and (A <= D)) or ((Z-A) <> 5);
The simple expressions resulting from this expression might be:
Temp2 := X = Y
Temp := A <= D
Temp := Temp and Temp2
Temp2 := Z-A
Temp2 := Temp2 <> 5
B := Temp or Temp2
The assembly language code for these expressions could be:
mov ax, x ;See if X = Y and load zero or
cmp ax, y ; one into AX to denote the result
jnz L1 ; of this comparison.
mov al, 1 ;X = Y
jmp L2
L1: mov al, 0 ;X <> Y
L2:
mov bx, A ;See if A <= D and load zero or one
cmp bx, D ; into BX to denote the result of
jle ST1 ; this comparison.
mov bl, 0
jmp L3
ST1: mov bl, 1
L3:
and bl, al ;Temp := Temp and Temp2
mov ax, Z ;See if (Z-A) <> 5.
sub ax, A ;Temp2 := Z-A;
cmp ax, 5 ;Temp2 := Temp2 <> 5;
jnz ST2
mov al, 0
jmp short L4
ST2: mov al, 1
L4:
or al, bl ;Temp := Temp or Temp2;
mov B, al ;B := Temp;
As you can see, this is a rather unwieldy sequence of statements. One slight
optimization you can use is to assume a result is going to be true or false
and initialize the corresponding boolean result ahead of time:
mov bl, 0 ;Assume X <> Y
mov ax, x
cmp ax, Y
jne L1
mov bl, 1 ;X is equal to Y, so make this true.
L1:
mov bh, 0 ;Assume not (A <= D)
mov ax, A
cmp ax, D
jnle L2
mov bh, 1 ;A <= D so make this true
L2:
and bl, bh ;Compute logical AND of results.
mov bh, 0 ;Assume (Z-A) = 5
mov ax, Z
sub ax, A
cmp ax, 5
je L3:
mov bh, 1 ;(Z-A) <> 5
L3:
or bl, bh ;Logical OR of results.
mov B, bl ;Save boolean result.
Of course, if you have an 80386 or later processor, you can use the setcc
instructions to simplify this a bit:
mov ax, x
cmp ax, y
sete al ;TEMP2 := X = Y
mov bx, A
cmp bx, D
setle bl ;TEMP := A <= D
and bl, al ;Temp := Temp and Temp2
mov ax, Z
sub ax, A ;Temp2 := Z-A;
cmp ax, 5 ;Temp2 := Temp2 <> 5;
setne al
or bl, al ;Temp := Temp or Temp2;
mov B, bl ;B := Temp;
This code sequence is obviously much better than the previous one, but it
will only execute on 80386 and later processors.
Another way to handle boolean expressions is to represent boolean values
by states within your code. The basic idea is to forget maintaining a boolean
variable throughout the execution of a code sequence and use the position
within the code to determine the boolean result. Consider the following
implementation of the above expression. First, let's rearrange the expression
to be
B := ((Z-A) <> 5) or ((X=Y) and (A <= D));
This is perfectly legal since the or operation is commutative. Now consider
the following implementation:
mov B, 1 ;Assume the result is true.
mov ax, Z ;See if (Z-A) <> 5
sub ax, A ;If this condition is true, the
cmp ax, 5 ; result is always true so there
jne Done ; is no need to check the rest.
mov ax, X ;If X <> Y, the result is false,
cmp ax, Y ; no matter what A and D contain
jne SetBtoFalse
mov ax, A ;Now see if A <= D.
cmp ax, D
jle Done ;If so, quit.
SetBtoFalse: mov B, 0 ;If B is false, handle that here.
Done:
Notice that this section of code is a lot shorter than the first version
above (and it runs on all processors). The previous translations did everything
computationally. This version uses program flow logic to improve the code.
It begins by assuming a true result and sets the B variable
to true. It then checks to see if (Z-A) <> 5. If this
is true the code branches to the done table because B is true
no matter what else happens. If the program falls through to the mov
ax, X instruction, we know that the result of the previous comparison
is false. There is no need to save this result in a temporary since we implicitly
know its value by the fact that we're executing the mov ax, X
instruction. Likewise, the second group of statements above checks to see
if X is equal to Y. If it is not, we already know
the result is false so this code jumps to the SetBtoFalse label.
If the program begins executing the third set of statements above, we know
that the first result was false and the second result was true; the position
of the code guarantees this. Therefore, there is no need to maintain temporary
boolean variables that keep track of the state of this computation.
Consider another example:
B := ((A = E) or (F <> D)) and ((A<>B) or (F = D));
Computationally, this expression would yield a considerable amount of code.
However, by using flow control you can reduce it to the following:
mov b, 0 ;Assume result is false.
mov ax, a ;See if A = E.
cmp ax, e
je test2 ;If so, 1st subexpression is true.
mov ax, f ;If not, check 2nd subexpression
cmp ax, d ; to see if F <> D.
je Done ;If so, we're done, else fall
; through to next tests.
Test2: mov ax, a ;Does A <> B?
cmp ax, b
jne SetBto1 ;If so, we're done.
mov ax, f ;If not, see if F = D.
cmp ax, d
jne Done
SetBto1: mov b, 1
Done:
There is one other difference between using control flow vs. computation
logic: when using control flow methods, you may skip the majority of the
instructions that implement the boolean formula. This is known as short-circuit
evaluation. When using the computation model, even with the setcc
instruction, you wind up executing most of the statements. Keep in
mind that this is not necessarily a disadvantage. On pipelined processors
it may be much faster to execute several additional instructions rather
than flush the pipeline and prefetch queue. You may need to experiment with
your code to determine the best solution.
When working with boolean expressions don't forget the that you might be
able to optimize your code by simplifying those boolean expressions (See
Chapter Two). You can use algebraic transformations (especially DeMorgan's
theorems) and the mapping method to help reduce the complexity of an expression.
- 9.2 - Logical (Boolean) Expressions
Art of Assembly: Chapter Nine - 27 SEP 1996
[Chapter Nine][Previous] [Next]
[Art of Assembly][Randall
Hyde]